package com.zs.letcode.binary_search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 找到 K 个最接近的元素
 * 给定一个排序好的数组arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。
 * <p>
 * 整数 a 比整数 b 更接近 x 需要满足：
 * <p>
 * |a - x| < |b - x| 或者
 * |a - x| == |b - x| 且 a < b
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：arr = [1,2,3,4,5], k = 4, x = 3
 * 输出：[1,2,3,4]
 * 示例 2：
 * <p>
 * 输入：arr = [1,2,3,4,5], k = 4, x = -1
 * 输出：[1,2,3,4]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= k <= arr.length
 * 1 <= arr.length<= 104
 * 数组里的每个元素与x 的绝对值不超过 104
 * 相关标签
 * 数组
 * 双指针
 * 二分查找
 * 排序
 * 堆（优先队列）
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/binary-search/xeve4m/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/7/30 10:07
 */
public class Chapter9 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.findClosestElements(new int[]{1, 2, 3, 4, 5}, 4, 3);
    }

    private static class Solution {
        /**
         * 方法 1： 使用 Collection.sort()
         * 直观地，我们可以将数组中的元素按照与目标 x 的差的绝对值排序，排好序后前 k 个元素就是我们需要的答案。
         *
         * @param arr
         * @param k
         * @param x
         * @return
         */
        public List<Integer> findClosestElements(int[] arr, int k, int x) {
            List<Integer> ret = Arrays.stream(arr).boxed().collect(Collectors.toList());
            Collections.sort(ret, (a, b) -> a.equals(b) ? a - b : Math.abs(a - x) - Math.abs(b - x));
            ret = ret.subList(0, k);
            Collections.sort(ret);
            return ret;
        }

        /**
         * 方法一：排除法（双指针）
         */
        public List<Integer> findClosestElements1(int[] arr, int k, int x) {
            int size = arr.length;
            int left = 0, right = size - 1;
            int removeNums = size - k;
            while (removeNums > 0) {
                if (x - arr[left] <= arr[right] - x) {
                    right--;
                } else {
                    left++;
                }
                removeNums--;
            }
            List<Integer> res = new ArrayList<>();
            for (int i = left; i < left + k; i++) {
                res.add(arr[i]);
            }
            return res;
        }
    }
}
